package com.zhanghp.class036;

import com.zhanghp.common.TreeNode;

/**
 * 二叉树按层序列化和反序列化<br/>
 * 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
 * <p>
 * 请设计一个算法来实现二叉树的序列化与反序列化。<br/>
 * 这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 * </p>
 *
 * @author zhanghp
 * @since 2024/4/18 11:35
 */
public class Code06_LevelorderSerializeAndDeserialize {

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode ze = new TreeNode(5);
        a.left = b;
        a.right = c;
        c.left = d;
        c.right = e;
        Codec codec = new Codec();
        String serialize = codec.serialize(ze);
        codec.deserialize(serialize);
    }

    public static class Codec {

        public int MAXN = 10001;

        public TreeNode[] queue = new TreeNode[MAXN];

        public int l, r;

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            if (root != null) {
                sb.append(root.val + ",");
                l = r = 0;
                queue[r++] = root;
                while (l < r) {
                    TreeNode node = queue[l++];
                    if (node.left != null) {
                        sb.append(node.left.val + ",");
                        queue[r++] = node.left;
                    } else {
                        sb.append("#,");
                    }
                    if (node.right != null) {
                        sb.append(node.right.val + ",");
                        queue[r++] = node.right;
                    } else {
                        sb.append("#,");
                    }
                }
            }
            return sb.toString();
        }


        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.compareTo("") == 0) {
                return null;
            }
            String[] split = data.split(",");
            int splitInext = 0;
            TreeNode root = generate(split[splitInext++]);
            l = r = 0;
            queue[r++] = root;
            // 索引不会越界的原因
            // 1，#，# （序列化时左右孩子为空，用#占位）
            while (l < r) {
                TreeNode node = queue[l++];
                node.left = generate(split[splitInext++]);
                node.right = generate(split[splitInext ++]);
                if (node.left != null) {
                    queue[r ++] = node.left;
                }
                if (node.right != null) {
                    queue[r ++] = node.right;
                }

            }
            return root;
        }

        public TreeNode generate(String val) {
            return val.compareTo("#") == 0 ? null : new TreeNode(Integer.parseInt(val));
        }
    }

}
